#include <stdio.h>
#include <math.h>

#include "BasicRedBlackTree.h"
#include "System.h"
#include "BasicLinkedList.h"
#include "Exception.h"

#define CHECK_RB_TREE_ASSUMPTIONS
#define DEBUG_ASSERT

namespace illib {
	namespace BasicRedBlackTree{
		Node::Node() :
			color_(0),
			left_(0),
			right_(0),
			parent_(0)
		{
		}

		Node::~Node() {
		}

		bool Tree::lesser(Node& left, Node& right, TreeFunctions &functions){
			if (&left == &root_) return false;
			if (&right == &nil_) return false;
			if (&left == &nil_) return true;
			if (&right == &root_) return true;
			return functions.lesser(left, right);
		}

		bool Tree::greater(Node& left, Node& right, TreeFunctions &functions){
			if (&left == &root_) return true;
			if (&right == &nil_) return true;
			if (&left == &nil_) return false;
			if (&right == &root_) return false;
			return functions.greater(left, right);
		}

		bool Tree::equal(Node& left, Node& right, TreeFunctions &functions){
			if ((&left == &root_) && (&right == &root_)) return true;
			if ((&left == &nil_) && (&right == &nil_)) return true;
			if ((&left == &root_) || (&right == &root_)) return false;
			if ((&left == &nil_) || (&right == &nil_)) return false;
			return functions.equal(left, right);
		}

		bool Tree::lesserOrEqual(Node& left, Node& right, TreeFunctions &functions){
			return lesser(left, right, functions) || equal(left, right, functions);
		}

		bool Tree::greaterOrEqual(Node& left, Node& right, TreeFunctions &functions){
			return greater(left, right, functions) || equal(left, right, functions);
		}

		Tree::Tree() :
			length_(0)

		{
			nil_.left_ = nil_.right_ = nil_.parent_ = &nil_;
			nil_.color_ = 0;

			root_.parent_ = root_.left_ = root_.right_ = &nil_;
			root_.color_ = 0;
		}
		void Tree::clear() {
			nil_.left_ = nil_.right_ = nil_.parent_ = &nil_;
			nil_.color_ = 0;

			root_.parent_ = root_.left_ = root_.right_ = &nil_;
			root_.color_ = 0;
		}

		void Tree::left(Node& x) {
			Node* y;
			y = x.right_;
			x.right_ = y->left_;

			if (y->left_ != &nil_)
				y->left_->parent_ = &x;

			y->parent_ = x.parent_;

			if (&x == x.parent_->left_) {
				x.parent_->left_ = y;
			} else {
				x.parent_->right_ = y;
			}
			y->left_ = &x;
			x.parent_ = y;

#ifdef CHECK_RB_TREE_ASSUMPTIONS
			CheckAssumptions();
#endif
#ifdef DEBUG_ASSERT
			assert(!nil_.color_,"nil not red in RedBlackTree::LeftRotate");
#endif
		}

		void Tree::right(Node& y) {
			Node* x;
			x = y.left_;
			y.left_ = x->right_;

			if (&nil_ != x->right_)
				x->right_->parent_ = &y;

			x->parent_ = y.parent_;
			if (&y == y.parent_->left_) {
				y.parent_->left_ = x;
			} else {
				y.parent_->right_ = x;
			}
			x->right_ = &y;
			y.parent_ = x;

#ifdef CHECK_RB_TREE_ASSUMPTIONS
			CheckAssumptions();
#endif
#ifdef DEBUG_ASSERT
			assert(!nil_.color_,"nil not red in RedBlackTree::RightRotate");
#endif
		}

		Node * Tree::add(Node & entry, TreeFunctions &functions) {
			Node * x;
			x = &entry;
			{
				Node* y;
				Node* z;

				x->left_ = x->right_ = &nil_;
				z = &root_;
				y = root_.left_;
				while (y != &nil_) {
					z = y;
					if (greater(*y,*x, functions)) {
						y = y->left_;
					} else { /* x->key <= z.key */
						y = y->right_;
					}
				}
				x->parent_ = z;
				if ((z == &root_) || (greater(*z,*x, functions))) {
					z->left_ = x;
				} else {
					z->right_ = x;
				}

#ifdef DEBUG_ASSERT
				assert(!nil_.color_,"nil not red in RedBlackTree::TreeInsertHelp");
#endif
			}
			Node * y;
			Node * node;
			node = x;
			x->color_ = 1;
			while (x->parent_->color_) {
				if (x->parent_ == x->parent_->parent_->left_) {
					y = x->parent_->parent_->right_;
					if (y->color_) {
						x->parent_->color_ = 0;
						y->color_ = 0;
						x->parent_->parent_->color_ = 1;
						x = x->parent_->parent_;
					} else {
						if (x == x->parent_->right_) {
							x = x->parent_;
							left(*x);
						}
						x->parent_->color_ = 0;
						x->parent_->parent_->color_ = 1;
						right(*(x->parent_->parent_));
					}
				} else {
					y = x->parent_->parent_->left_;
					if (y->color_) {
						x->parent_->color_ = 0;
						y->color_ = 0;
						x->parent_->parent_->color_ = 1;
						x = x->parent_->parent_;
					} else {
						if (x == x->parent_->left_) {
							x = x->parent_;
							right(*x);
						}
						x->parent_->color_ = 0;
						x->parent_->parent_->color_ = 1;
						left(*(x->parent_->parent_));
					}
				}
			}
			root_.left_->color_ = 0;
			length_++;
			return (node);

#ifdef CHECK_RB_TREE_ASSUMPTIONS
			CheckAssumptions();
#endif
#ifdef DEBUG_ASSERT
			assert(!nil_.color_,"nil not red in RedBlackTree::Insert");
			assert(!root_.color_,"root not red in RedBlackTree::Insert");
#endif
		}

		Node * Tree::successor(Node & entry) {
			Node* x = &entry;
			Node* y;

			if (&nil_ != (y = x->right_)) {
				while (y->left_ != &nil_) {
					y = y->left_;
				}
				return (y);
			} else {
				y = x->parent_;
				while (x == y->right_) {
					if ((y == &root_) || (y == &nil_)) return y;
					x = y;
					y = y->parent_;
				}
				return (y);
			}
		}

		Node * Tree::predecessor(Node & entry) {
			Node* x = &entry;
			Node* y;

			if (&nil_ != (y = x->left_)) {
				while (y->right_ != &nil_) {
					y = y->right_;
				}
				return (y);
			} else {
				y = x->parent_;
				while (x == y->left_) {
					if ((y == &root_) || (y == &nil_)) return y;
					x = y;
					y = y->parent_;
				}
				return (y);
			}
		}

		Tree::~Tree() {

		}
		size_t Tree::length(){
			return length_;
		}
		void Tree::remove_(Node &node) {
			Node * x = &node;
			Node * w;
			Node * rootLeft = root_.left_;

			while ((!x->color_) && (rootLeft != x)) {
				if (x == x->parent_->left_) {
					w = x->parent_->right_;
					if (w->color_) {
						w->color_ = 0;
						x->parent_->color_ = 1;
						left(*(x->parent_));
						w = x->parent_->right_;
					}
					if ((!w->right_->color_) && (!w->left_->color_)) {
						w->color_ = 1;
						x = x->parent_;
					} else {
						if (!w->right_->color_) {
							w->left_->color_ = 0;
							w->color_ = 1;
							right(*w);
							w = x->parent_->right_;
						}
						w->color_ = x->parent_->color_;
						x->parent_->color_ = 0;
						w->right_->color_ = 0;
						left(*(x->parent_));
						x = rootLeft;
					}
				} else {
					w = x->parent_->left_;
					if (w->color_) {
						w->color_ = 0;
						x->parent_->color_ = 1;
						right(*(x->parent_));
						w = x->parent_->left_;
					}
					if ((!w->right_->color_) && (!w->left_->color_)) {
						w->color_ = 1;
						x = x->parent_;
					} else {
						if (!w->left_->color_) {
							w->right_->color_ = 0;
							w->color_ = 1;
							left(*w);
							w = x->parent_->left_;
						}
						w->color_ = x->parent_->color_;
						x->parent_->color_ = 0;
						w->left_->color_ = 0;
						right(*(x->parent_));
						x = rootLeft;
					}
				}
			}
			x->color_ = 0;

#ifdef CHECK_RB_TREE_ASSUMPTIONS
			CheckAssumptions();
#endif
#ifdef DEBUG_ASSERT
			assert(!nil_.color_,"nil not black in RedBlackTree::DeleteFixUp");
#endif
		}


		Node * Tree::remove(Node & z) {
			Node* y;
			Node* x;
			Node * returnValue = &z;

			y = ((z.left_ == &nil_) || (z.right_ == &nil_)) ? &z : successor(z);
			x = (y->left_ == &nil_) ? y->right_ : y->left_;
			if (&root_ == (x->parent_ = y->parent_)) {
				root_.left_ = x;
			} else {
				if (y == y->parent_->left_) {
					y->parent_->left_ = x;
				} else {
					y->parent_->right_ = x;
				}
			}
			if (y != &z) {

#ifdef DEBUG_ASSERT
				assert( (y!=&nil_),"y is nil in DeleteNode \n");
#endif

				y->left_ = z.left_;
				y->right_ = z.right_;
				y->parent_ = z.parent_;
				z.left_->parent_ = z.right_->parent_ = y;
				if (&z == z.parent_->left_) {
					z.parent_->left_ = y;
				} else {
					z.parent_->right_ = y;
				}
				if (!(y->color_)) {
					y->color_ = z.color_;
					remove_(*x);
				} else
					y->color_ = z.color_;
#ifdef CHECK_RB_TREE_ASSUMPTIONS
				CheckAssumptions();
#endif
#ifdef DEBUG_ASSERT
				assert(!nil_.color_,"nil not black in RedBlackTree::remove");
#endif
			} else {
				if (!(y->color_))
					remove_(*x);
#ifdef CHECK_RB_TREE_ASSUMPTIONS
				CheckAssumptions();
#endif
#ifdef DEBUG_ASSERT
				assert(!nil_.color_,"nil not black in RedBlackTree::remove");
#endif
			}
			length_--;
			return returnValue;
		}

		/*
		LinkedList * RedBlackTree::Enumerate(int low, int high) {
			TemplateStack<RedBlackTreeNode *> * enumResultStack = new TemplateStack<RedBlackTreeNode *> (4);

			RedBlackTreeNode* x = root.left_;
			RedBlackTreeNode* lastBest = NULL;

			while (nil != x) {
				if (x->key_ > high) {
					x = x->left_;
				} else {
					lastBest = x;
					x = x->right_;
				}
			}
			while ((lastBest) && (low <= lastBest->key_)) {
				enumResultStack->Push(lastBest);
				lastBest = predecessor(lastBest);
			}
			return (enumResultStack);
		}
		 */

		Iterator::Iterator(Node &node, Tree & tree, TreeFunctions &functions, bool forward) :
				tree_(tree),
				functions_(functions),
				x_(0),
				lastBest_(0),
				high_(node),
				low_(node),
				current_(0),
				forward_(forward)
		{
			init();
		}
		Iterator::Iterator(Node &low, Node &high, Tree & tree, TreeFunctions &functions, bool forward) :
				tree_(tree),
				functions_(functions),
				x_(0),
				lastBest_(0),
				high_(high),
				low_(low),
				current_(0),
				forward_(forward)
		{
			init();
		}
		Iterator::Iterator(Tree & tree, TreeFunctions &functions, bool forward) :
				tree_(tree),
				functions_(functions),
				x_(0),
				lastBest_(0),
				high_(tree.root_),
				low_(tree.nil_),
				current_(0),
				forward_(forward)
		{
			init();
		}
		Node * Iterator::current(){
			return current_;
		}

		void Iterator::init(){
			if(forward_){
				x_ = tree_.root_.left_;
				while (&tree_.nil_ != x_) {
					if (tree_.lesser(*x_, low_, functions_)) {
						x_ = x_->right_;
					} else {
						lastBest_ = x_;
						x_ = x_->left_;
					}
				}
			} else {
				x_ = tree_.root_.left_;
				while (&tree_.nil_ != x_) {
					if (tree_.greater(*x_, high_, functions_)) {
						x_ = x_->left_;
					} else {
						lastBest_ = x_;
						x_ = x_->right_;
					}
				}
			}
			next();
		}

		Node * Iterator::next(){
			if(forward_) {
				while ((lastBest_) && (tree_.greaterOrEqual(high_, *lastBest_, functions_))) {
					Node * value = lastBest_;
					lastBest_ = tree_.successor(*lastBest_);
					current_ = value;
					if (current_ == &tree_.nil_) current_ = 0;
					if (current_ == &tree_.root_) current_ = 0;
					return value;
				}
				current_ = 0;
				return 0;
			} else {
				while ((lastBest_) && (tree_.lesserOrEqual(low_, *lastBest_, functions_))) {
					Node * value = lastBest_;
					lastBest_ = tree_.predecessor(*lastBest_);
					current_ = value;
					if (current_ == &tree_.nil_) current_ = 0;
					if (current_ == &tree_.root_) current_ = 0;
					return value;
				}
				current_ = 0;
				return 0;
			}
		}

		void Tree::CheckAssumptions() {
			assert(nil_.color_ == 0);
			assert(root_.color_ == 0);
		}
	};
}

